/**
*	@file QueryOptimizer.cpp
*
*	@brief this header file is for query optimizer which is indenpendent from query evaluator
*
*	@author li yuchen
*
*	@date 1/28/2011
*/
#include "QueryOptimizer.h"
#include "QueryTree.h"
#include "PKB.h"
#include <set>
#include <algorithm>

bool optimize_stop = false;

static enum ErrorType{
	SepQueryClause
};

// print out the error message if the optimizer occurs
static void PrintErrorMessage(ErrorType type);

// call this function if the optimizer should stop
static void OptimizeStop();

// remove all the constant query with left hand side is constant
// also optimize for affect star and next star
static void ReplaceConstantOptimize();

// elimiate duplicate query clause from the query tree
static void EliminateDuplicateQuery();

// put all the bool query clause at front
static void FrontBoolQueryClause();

// sort the query based on their priority
static void SortQueryClause();
static bool CompareQueryPriority(QueryTNode* arg_a, QueryTNode* arg_b);

// seperate the query clauses into clusters;
static void SeperateQueryClause();

// further seperate the clause if the clusters are too large
static void FurtherSeperateClause();

void OptimizeQuery(){
	if(!optimize_stop) ReplaceConstantOptimize();
	
	if(!optimize_stop){	
		EliminateDuplicateQuery();
		FrontBoolQueryClause();
		SeperateQueryClause();
		//FurtherSeperateClause();
	}
	//cout << QueryTree::ToString();
}

void ReplaceConstantOptimize(){
	int i = 0;

	while(true){
		QueryArgumentValue replace_query_var = 0;
		QueryArgumentValue replace_value = 0;
		string replace_string;

		int call_replace = 0;
		// 0: no call replace 
		// 1: string# call replace
		// 2: stmt# call replace;

		// replace all the variable with avaiable constants
		for(;i < QueryTree::get_vp_query_tnodes()->size(); i++){
			QueryTNode* traverser = (*QueryTree::get_vp_query_tnodes())[i];
			call_replace = 0;
			if(traverser->q_type == COMPARE && traverser->argument_a * traverser->argument_b < 0){
				if(traverser->argument_a > 0){
					replace_query_var = traverser->argument_a;
					replace_value = traverser->argument_b;
					switch(QueryVarTable::GetQueryVarType(traverser->argument_a)){
					case VAR_TYPE:
						replace_string = VarTable::GetVarName(abs(traverser->argument_b)); break;
					case PROC_TYPE:
						replace_string = ProcTable::GetProcName(abs(traverser->argument_b));break;
					case CALL_TYPE:
						if(traverser->special_type == PROC_TYPE){
							call_replace = 1;
							replace_string =  ProcTable::GetProcName(abs(traverser->argument_b));
						}
						else call_replace = 2;
						break;
					}
					break;
				}
				else if(traverser->argument_b > 0){
					replace_query_var = traverser->argument_b;
					replace_value = traverser->argument_a;
					switch(QueryVarTable::GetQueryVarType(traverser->argument_b)){
					case VAR_TYPE:
						replace_string = VarTable::GetVarName(abs(traverser->argument_a)); break;
					case PROC_TYPE:
						replace_string = ProcTable::GetProcName(abs(traverser->argument_a)); break;
					case CALL_TYPE:
						if(traverser->special_type == PROC_TYPE){
							call_replace = 1;
							replace_string =  ProcTable::GetProcName(abs(traverser->argument_a));
						}
						else call_replace = 2;
						break;
					}
					break;
				}
			}
		}
		if(replace_query_var == 0) break;

		// start to replace the variable
		bool replaced = false;
		for(int j = 0; j < QueryTree::get_vp_query_tnodes()->size(); j++){
			if(i == j) continue;
			QueryTNode* replacer = (*QueryTree::get_vp_query_tnodes())[j];
			if(call_replace == 0){
				if(replacer->q_type == COMPARE && replacer->argument_a > 0 && replacer->argument_b > 0){
					QueryVarType type_a = QueryVarTable::GetQueryVarType(replacer->argument_a);
					QueryVarType type_b = QueryVarTable::GetQueryVarType(replacer->argument_b);
					if(type_a == PROC_TYPE && type_b == VAR_TYPE){
						if(replacer->argument_a == replace_query_var) replace_value = VarTable::GetVarIdx(replace_string);
						else if(replacer->argument_b == replace_query_var)  replace_value = ProcTable::GetProcIdx(replace_string);
						if(replace_value < 0){
							OptimizeStop();
							return;
						}
						replace_value = -replace_value;
					}else if(type_a == VAR_TYPE && type_b == PROC_TYPE){
						if(replacer->argument_a == replace_query_var) replace_value = ProcTable::GetProcIdx(replace_string);
						else if(replacer->argument_b == replace_query_var)  replace_value = VarTable::GetVarIdx(replace_string);
						if(replace_value < 0){
							OptimizeStop();
							return;
						}
						replace_value = -replace_value;
					}
				}
				if(replacer->argument_a == replace_query_var){
					replacer->argument_a = replace_value;
					replaced = true;
				}
				if(replacer->argument_b == replace_query_var){
					replacer->argument_b = replace_value;
					replaced = true;
				}
			}
			else if(call_replace == 1){
				if(replacer->q_type == COMPARE && replacer->special_type == PROC_TYPE){
					if(replacer->argument_a == replace_query_var){
						if(replacer->argument_b > 0){
							if(QueryVarTable::GetQueryVarType(replacer->argument_b) == VAR_TYPE){
								replace_value = VarTable::GetVarIdx(replace_string);
								replace_value = -replace_value;
							}
							if(replace_value > 0){
								OptimizeStop();
								return;
							}
						}
						replacer->argument_a = replace_value;
						replaced = true;
					}
					if(replacer->argument_b == replace_query_var){
						if(replacer->argument_a > 0){
							if(QueryVarTable::GetQueryVarType(replacer->argument_a) == VAR_TYPE){
								replace_value = VarTable::GetVarIdx(replace_string);
								replace_value = -replace_value;
							}
							if(replace_value > 0){
								OptimizeStop();
								return;
							}
						}
						replacer->argument_b = replace_value;
						replaced = true;
					}
				}
			}
			else if(call_replace == 2){
				if((replacer->q_type == COMPARE && replacer->special_type != PROC_TYPE) || replacer->q_type != COMPARE ){
					if(replacer->argument_a == replace_query_var){
						replacer->argument_a = replace_value;
						replaced = true;
					}
					if(replacer->argument_b == replace_query_var){
						replacer->argument_b = replace_value;
						replaced = true;
					}
				}
			}
			// eliminate case where something = 0 if something is not constant
			if(replacer->q_type == COMPARE){
				if(replacer->argument_a == 0){
					if(replacer->argument_b > 0){
						if(QueryVarTable::GetQueryVarType(replacer->argument_b) != CONST_TYPE){
							OptimizeStop();
							return;
						}
					}
				}else if(replacer->argument_b == 0){
					if(replacer->argument_a > 0){
						if(QueryVarTable::GetQueryVarType(replacer->argument_a) != CONST_TYPE){
							OptimizeStop();
							return;
						}
					}
				}
			}
		}
		if(replaced) i = 0; // rescan the query clauses
		else i++; // continue next clause
	}


	// start to eliminate redundant query and find wrong query
	vector<QueryTNode*>::iterator iter = QueryTree::get_vp_query_tnodes()->begin();//QueryTree::get_vp_query_tnodes().begin();
	while( iter != QueryTree::get_vp_query_tnodes()->end()){
		if((*iter)->q_type == COMPARE){
			if((*iter)->argument_a < 0 && (*iter)->argument_b < 0){
				if((*iter)->argument_a == (*iter)->argument_b){
					iter = QueryTree::get_vp_query_tnodes()->erase(iter);
					continue;
				}
				else{
					OptimizeStop();
					break;
				}
			}
			// do the swap
			else if((*iter)->argument_a < 0 && (*iter)->argument_b > 0){
				int temp = (*iter)->argument_a;
				(*iter)->argument_a = (*iter)->argument_b;
				(*iter)->argument_b = temp;
			}
		}
		else if((*iter)->q_type == AFFECTS_ADV){
			if((*iter)->argument_a == 0 || (*iter)->argument_b == 0){
				(*iter)->q_type = AFFECTS;
			}
		}
		else if((*iter)->q_type == NEXT_ADV){
			if((*iter)->argument_a == 0 || (*iter)->argument_b == 0){
				(*iter)->q_type = NEXT;
			}
		}
		else if((*iter)->q_type == AFFECTSBIP_ADV){
			if((*iter)->argument_a == 0 || (*iter)->argument_b == 0){
				(*iter)->q_type = AFFECTSBIP;
			}
		}
		else if((*iter)->q_type == NEXTBIP_ADV){
			if((*iter)->argument_a == 0 || (*iter)->argument_b == 0){
				(*iter)->q_type = NEXTBIP;
			}
		}
		++iter;
	}
}

void FrontBoolQueryClause(){
	vector<QueryTNode*> new_query_node;

	vector<QueryTNode*>* original_query_tree = QueryTree::get_vp_query_tnodes();
	for(int i = 0; i < original_query_tree->size(); i++){
		if((*original_query_tree)[i]->argument_a <= 0 && (*original_query_tree)[i]->argument_b <= 0){
			new_query_node.insert(new_query_node.begin(),(*original_query_tree)[i]);
		}
		else{
			new_query_node.push_back((*original_query_tree)[i]);
		}
	}
	original_query_tree->clear();
	(*original_query_tree) = new_query_node;
}

void EliminateDuplicateQuery(){
	vector<QueryTNode*> new_query_tree;
	vector<QueryTNode*>* old_query_tree = QueryTree::get_vp_query_tnodes();

	for(unsigned int i = 0; i < old_query_tree->size(); i++){
		bool duplicate = false;
		QueryTNode* query_clause = (*old_query_tree)[i];
		for(unsigned int j = 0; j < new_query_tree.size(); j++){
			if(new_query_tree[j]->argument_a == query_clause->argument_a &&
				new_query_tree[j]->argument_b == query_clause->argument_b &&
				new_query_tree[j]->q_type == query_clause->q_type &&
				new_query_tree[j]->special_type == query_clause->special_type){
					if(new_query_tree[j]->q_type != PATTERN_Q) duplicate = true;
					else{
						if(new_query_tree[j]->pattern == NULL && query_clause->pattern == NULL) duplicate = true;
						else if(new_query_tree[j]->isRelaxed == query_clause->isRelaxed &&
							AST::IsPatternMatch(new_query_tree[j]->pattern,0,query_clause->pattern,false)) duplicate = true;
					}
					if(duplicate) break;
			}
			if(query_clause->argument_a > 0 && query_clause->argument_b > 0 && query_clause->q_type == COMPARE){
				if(new_query_tree[j]->argument_a == query_clause->argument_b &&
					new_query_tree[j]->argument_b == query_clause->argument_a &&
					new_query_tree[j]->q_type == query_clause->q_type &&
					new_query_tree[j]->special_type == query_clause->special_type){
						duplicate = true;
						break;
				}
			}
		}
		if(!duplicate) new_query_tree.push_back(query_clause);
	}

	old_query_tree->clear();
	(*old_query_tree) = new_query_tree;
}

void SortQueryClause(vector<QueryTNode*>& query_vector){
	sort(query_vector.begin(),query_vector.end(),CompareQueryPriority);
}

bool CompareQueryPriority(QueryTNode* arg_a, QueryTNode* arg_b){
	return (arg_a->priority < arg_b->priority);
}

void SeperateQueryClause(){
	vector<QueryTNode*> query_tree;
	for(int i = 0; i < QueryTree::get_vp_query_tnodes()->size(); i++){
		if((*QueryTree::get_vp_query_tnodes())[i]->argument_a > 0 || (*QueryTree::get_vp_query_tnodes())[i]->argument_b > 0){
			query_tree.push_back((*QueryTree::get_vp_query_tnodes())[i]);
		}
	}

	while(query_tree.size() != 0){
		// iter_set iterate through each query indexes set for a given query cluster
		// matches with new_arg_cluster
		set<int>::iterator iter_set;
		// iter_query_clause takes care the query_var vector
		// matches with new_query_cluster
		vector<QueryTNode*>::iterator iter_query_clause;

		vector<QueryTNode*> new_query_cluster;
		new_query_cluster.push_back(query_tree[0]);
		set<QueryArgumentValue> new_arg_cluster;
		if(query_tree[0]->argument_a > 0) 
			new_arg_cluster.insert(query_tree[0]->argument_a);
		if(query_tree[0]->argument_b > 0) 
			new_arg_cluster.insert(query_tree[0]->argument_b);

		query_tree.erase(query_tree.begin());
		iter_query_clause = query_tree.begin();

		// indict whether the loop should stop
		bool set_increase = false;

		while(iter_query_clause !=  query_tree.end()){
			if((*iter_query_clause)->argument_a > 0){
				iter_set = new_arg_cluster.find((*iter_query_clause)->argument_a);
				if(iter_set != new_arg_cluster.end()){
					if((*iter_query_clause)->argument_b > 0) new_arg_cluster.insert((*iter_query_clause)->argument_b);
					set_increase = true;
				}else{
					if((*iter_query_clause)->argument_b > 0){
						iter_set = new_arg_cluster.find((*iter_query_clause)->argument_b);
						if(iter_set != new_arg_cluster.end()){
							new_arg_cluster.insert((*iter_query_clause)->argument_a);
							set_increase = true;
						}
					}
				}
			}else if((*iter_query_clause)->argument_b > 0){
				iter_set = new_arg_cluster.find((*iter_query_clause)->argument_b);
				if(iter_set != new_arg_cluster.end()) set_increase = true;
			}
			if(set_increase){
				new_query_cluster.push_back((*iter_query_clause));
				query_tree.erase(iter_query_clause);
				iter_query_clause =  query_tree.begin();
				set_increase = false;
				continue;
			}
			++iter_query_clause;
		}

		QueryTree::get_p_query_matrix()->push_back(new_query_cluster);
	}
}

void PrintErrorMessage(ErrorType type){
	cout << "Query Optimizer problem" << endl;
	switch(type){
	case SepQueryClause:
		break;
	}
}

void OptimizeStop(){
	QueryTNode* stop_node = new QueryTNode;
	stop_node->q_type = STOP;
	stop_node->pattern = NULL;
	QueryTree::get_vp_query_tnodes()->insert(QueryTree::get_vp_query_tnodes()->begin(),stop_node);
	optimize_stop = true;
}

void FurtherSeperateClause(){
	if(QueryTree::get_p_query_matrix()->size() > 2 * GetNumCPUs()) return;
	bool further_seperate = false;
	for(int i = 0; i < QueryTree::get_p_query_matrix()->size(); i++){
		if(QueryTree::get_p_query_matrix()[i].size() > 1){
			further_seperate = true;
		}
	}
	if(!further_seperate) return;

	double average_size = ((double)QueryTree::get_size()) / QueryTree::get_p_query_matrix()->size();

	vector<vector<QueryTNode*>> new_query_cluster;
	for(unsigned int i = 0; i < QueryTree::get_p_query_matrix()->size(); i++){
		if((double)(*QueryTree::get_p_query_matrix())[i].size() > 2 * average_size){
			vector<QueryTNode*> sub_cluster_a;
			vector<QueryTNode*> sub_cluster_b;
			for(unsigned int j = 0; j < (*QueryTree::get_p_query_matrix())[i].size(); j++){
				if( j <= (*QueryTree::get_p_query_matrix())[i].size() / 2 - 1) sub_cluster_a.push_back((*QueryTree::get_p_query_matrix())[i][j]);
				else sub_cluster_b.push_back((*QueryTree::get_p_query_matrix())[i][j]);
			}
			new_query_cluster.push_back(sub_cluster_a);
			new_query_cluster.push_back(sub_cluster_b);
		}
		else new_query_cluster.push_back((*QueryTree::get_p_query_matrix())[i]);
	}

	// clear content and assign new cluster
	for(unsigned int i = 0; i < QueryTree::get_p_query_matrix()->size(); i++)
		(*QueryTree::get_p_query_matrix())[i].clear();
	QueryTree::get_p_query_matrix()->clear();
	(*QueryTree::get_p_query_matrix()) = new_query_cluster;
}


